
//题目链接：https://leetcode.cn/problems/multiply-strings/description/

class Solution {
public:
    string multiply(string num1, string num2) {

        int n1 = num1.size(), n2 = num2.size();
        vector<int> v1, v2, vv(n1 + n2);
        v1.reserve(n1);
        v2.reserve(n2);

        //把字符串的每个字符插入到数组中
        for (int i = n1 - 1; i >= 0; i--)
            v1.push_back(num1[i] - '0');

        for (int i = n2 - 1; i >= 0; i--)
            v2.push_back(num2[i] - '0');

        for (int i = 0; i < n1; i++)
        {
            for (int j = 0; j < n2; j++)
            {
                vv[i + j] += v1[i] * v2[j];
            }
        }

        int t = 0; //存放进制
        for (int i = 0; i < vv.size(); i++)
        {
            vv[i] += t;       //给vv[i]加上进制
            t = vv[i] / 10;     //取vv[i]的进制
            vv[i] %= 10;      //取vv[i]的个位
        }

        //去除前导0
        int k = vv.size() - 1;
        while (k > 0 && !vv[k])
            k--;


        string str; //装运算的结果
        str.reserve(k + 1);
        for (int i = k; k >= 0; k--)
        {
            str.push_back(vv[k] + '0');
        }

        return str;
    }
};